//Taken and modified with permission from Dr. Selinski's code repository.

// Set.cpp
// templated set class using singly linked list
// the header and implementation are combined because of templates

#ifndef _SET_H
#define _SET_H

#include "Node.cpp"
#include <iostream>
#include <string>
#include <cstdlib>

using std::string;
using std::ostream;
using std::endl;

template <class S> class SetIter;   // forward declaration

/* template class definition (interface) comes first */

template <class S>
class Set 
{
public:
  Set();			// default constructor
  Set(S n);    // make a set with single value n in it
  Set(const Set<S> & is);	// copy constructor - deep copy
  ~Set();			// destructor - memory cleanup
  
  // accessor functions
  
  int size() const;		// return size
  bool isMember(S n) const;
  ostream& display(ostream & os) const;	// print contents to os
  
  // mutator functions
  
  bool add(S n);		// add n to set if not there
  S remove(int toIndex);		// remove n from set if there
  void clear();			// clear elements from set
  
  const Set<S> & operator=(const Set<S> & is); // deep assign from is
  
private:
  int mysize;	// number of elements in set
  Node<S> * myset;	// head pointer to first item in set
  Node<S> * mytail;	// pointer to end of set
  
  void clone(Node<S>* & newhead, Node<S>* & newtail) const;	
  // return clone of this set's list through newhead and newtail
  
  friend class SetIter<S>;
  
}; // end of Set class definition -------------------------

// related free functions, overloaded operators -------------------

template <class S>
ostream & operator<<(ostream & os, const Set<S> & is);	

/* Now definitions of the methods must be in the same file 
   because of the template
*/

template <class S>
Set<S>:: Set()
   :  mysize(0),
      myset(NULL),
      mytail(NULL)
{ }

template <class S>
Set<S>:: Set(S n) 
   :  mysize(1),
      myset(new Node<S>(n)),
      mytail(myset)
{ }

template <class S>
Set<S>:: Set(const Set<S> & copyfrom)
   :  mysize(copyfrom.mysize),
      myset(NULL),
      mytail(NULL)
{
  copyfrom.clone(myset, mytail);
}

template <class S>
Set<S>:: ~Set()
{
  clear();
}

template <class S>
void Set<S>:: clear()
{
  mytail = myset;
  while (mytail != NULL)
    {
      mytail = mytail->next;
      delete myset;
      myset = mytail;
    }
  mysize = 0;
}

template <class S>
int Set<S>:: size() const
{
  return mysize;
}

/* assumes == and > overloaded for S class */
template <class S>
bool Set<S>:: isMember(S n) const
{
  Node<S> * aux = myset;
  while (aux != NULL)
    {	if (aux->info == n)
	return true;
      if (aux->info > n)	// ordered list assumption
	return false;
      aux = aux->next;
    }
  return false;
}

/* assumes << overloaded for S type */
template <class S>
ostream & Set<S>:: display(ostream & os) const
{
  Node<S> * temp = myset;
  while (temp)
    { os << temp->info << " ";
      temp = temp->next;
    }
  return os;
}

/* assumes < and == overloaded for S class */
template <class S>
bool Set<S>:: add(S n)	// maintain in order
{
  Node<S> * prev = NULL;
  Node<S> * after = myset;
  
  while (after != NULL && after->info < n)	// uses lazy evaluation
    {
      prev = after;
      after = after->next;
    }
  
  if (after == NULL)		// adding to end of list or empty list
    {
      if (prev == NULL)	// empty list
	{
	  myset = new Node<S>(n);
	  mytail = myset;
	}
      else		// add to end of list
	{
	  prev->next = new Node<S>(n);
	  mytail = prev->next;
	}
    }
  else // after->info > n       add between prev and after
    if (prev == NULL)	// add to beginning
      {	myset = new Node<S>(n, after);
      }
    else 		// add in middle
      {	prev->next = new Node<S>(n, after);
      }
  mysize++;
  return true;
}

/* assumes == and < overloaded for S class */
template <class S>
S Set<S>:: remove(int toIndex)
{
  Node<S> * prev = NULL;
  Node<S> * curr = myset;
  S toReturn;
  int index = 0;
  while (curr != NULL && index<toIndex)
    {
      prev = curr;
      curr = curr->next;
      index++;
    }
  if (curr != NULL)	// delete curr
    {
      toReturn = curr->info;
      if (prev == NULL)
        {	myset = curr->next;		// delete first item
        }
      else
        {	prev->next = curr->next;
        }
      if (curr == mytail) 
	mytail = prev;
      delete curr;
      mysize--;
      return toReturn;
    }
  return toReturn;
}

template <class S>
const Set<S> & Set<S>:: operator=(const Set<S> & rhs)	// deep assignment
{
  if (this != &rhs)	// prevent self assignment
    {
      clear();			// delete old set
      mysize = rhs.mysize;
      rhs.clone(myset, mytail);	// use clone to copy
    }
  return *this;
}

template <class S>
void Set<S>:: clone(Node<S>* & newhead, Node<S>* & newtail) const
// return clone of this set through parameters newhead and newtail
{
  Node<S> * copytemp = myset;
  Node<S> * newnode;
  
  newhead = newtail = NULL;
  while (copytemp)
    { newnode = new Node<S>(copytemp->info);
      if (newhead == NULL)
	newhead = newnode;
      if (newtail != NULL)
	newtail->next = newnode;
      newtail = newnode;
      copytemp = copytemp->next;
    }
}

// related free functions, overloaded operators ---------------------

template <class Q>
ostream & operator<<(ostream & os, const Set<Q> & is)	
{
  is.display(os);	  // pass the buck to existing member function
  return os;
}


#endif
